// https://www.bilibili.com/video/BV1d54y1f7B3?spm_id_from=333.788.player.switch&vd_source=d6fe65f095f01f05591e89d810720ccc&p=33
// 2024-10-25

public class P039_打家劫舍2_动态规划 {

    // 数组首尾相连（街道圆形）
    public static void main(String[] args) {
        System.out.println(fun(new int[] {2,7,9,3,1}));
    }

    // 在0 到 length-1 两个位置二选一
    private static int fun(int[] arr) {
        // 不取尾和不取头，两种情况选最大
        return Math.max(fun(arr,0,arr.length-2),fun(arr,1, arr.length-1));
    }

    private static int fun(int[] arr,int start,int end) {
        int[] dp = new int[arr.length];
        dp[start] = arr[start];
        dp[start+1] = Math.max(arr[start],arr[start+1]);

        for (int i = start+2; i <= end; i++) dp[i] = Math.max(arr[i] + dp[i-2],dp[i-1]);
        return dp[end];
    }

}
